import java.util.*;

/**
 * 380. 常数时间插入、删除和获取随机元素
 * https://leetcode-cn.com/problems/insert-delete-getrandom-o1/
 */
public class Solutions_380 {
    public static void main(String[] args) {
        RandomizedSet obj = new RandomizedSet();
        boolean res1 = obj.remove(0);  // output: false
        System.out.println(res1);
        boolean res2 = obj.remove(0);  // output: false
        System.out.println(res2);
        boolean res3 = obj.insert(0);  // output: true
        System.out.println(res3);
        int res4 = obj.getRandom();  // output: 0
        System.out.println(res4);
        boolean res5 = obj.remove(0);  // output: true
        System.out.println(res5);
        boolean res6 = obj.insert(0);  // output: true
        System.out.println(res6);
    }
}

/**
 * 解题关键：
 * 1. 使用 map 来定位元素在 list 中的索引进行 remove 操作
 * 2. 使用 random.nextInt(list.size()) 来返回随机元素
 */
class RandomizedSet {
    // map 记录某元素在 list 中的索引，方便直接定位索引并进行删除操作，省却遍历查找的时间
    Map<Integer, Integer> map;
    List<Integer> list;
    // 用于生成随机索引
    Random random;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        random = new Random();
        map = new HashMap<>();
        list = new ArrayList<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        // 通过 map 知道 val 在 list 中的索引
        int idx = map.get(val);
        map.remove(val);
        // 为什么不直接 list.remove(idx)？因为 remove 元素后，
        // list 会调用 System.arraycopy 方法来调整索引结构，浪费时间，提高了平均时间复杂度
        if (idx == list.size() - 1) {
            // 本身就是 list 最后一个元素时
            list.remove(idx);
            return true;
        }
        // 要删除的元素，不是最后一个元素时，将 idx 上的元素，替换为 list 列表的最后一个元素
        int lastElement = list.get(list.size() - 1);
        list.set(idx, lastElement);
        // 仅移除最后一个元素时，调整索引结构的时间将大大减少
        list.remove(list.size() - 1);
        // 重要：同时修改最后一个元素的索引为 idx
        map.put(lastElement, idx);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        // 随机索引范围 [0, list.size - 1]
        return list.get(random.nextInt(list.size()));
    }
}
